Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Лабораторна робота № 9
з дисципліни “Комп’ютерна графіка”
Тема: Простий алгоритм заповнення з запалом
Мета: Освоїти алгоритм заповнення гранично-визначеної області
ТЕОРЕТИЧНІ ОСНОВИ
ПОРЯДКОВИЙ АЛГОРИТМ ЗАПОВНЕННЯ З ЗАПАЛОМ
Даний алгоритм застосовується до гранично-визначених областей. Гранично-визначена 4-зв'язна область може бути як опуклою, так і не опуклою, а також може містити діри. В зовнішній області, пов'язаній з нашою гранично-визначеною областю, не повинно бути пікселів з кольором, яким заповнюється область чи багатокутник. Схематично роботу алгоритму можна розбити на чотири етапи.
Порядковий алгоритм заповнення з запалом
Затравочний піксел на інтервалі витягається зі стека, що містить затравочні піксели.
Інтервал із затравочним пікселем заповнюється вліво і вправо від запалу уздовж скануючого рядка доти, поки не буде знайдена границя. У змінних Хлів і Хправ запам'ятовуються крайній лівий і крайній правий піксели інтервалу.
У діапазоні Хлів<х<Хправ перевіряються рядки, розташовані безпосередньо над і під біжучим рядком. Визначається, чи є на них ще не заповнені піксели. Якщо такі піксели є (тобто не всі піксели граничні, чи уже заповнені), то в зазначеному діапазоні крайній правий зазначений піксел у кожнім інтервалі відзначається як затравочний і поміщується в стек.
При ініціалізації алгоритму в стек поміщується єдиний затравочний піксел, робота завершується при спустошенні стека. Алгоритм справляється з дірами і зубцями на границі.
Порядковий алгоритм заповнення з запалом
Запал (х, у) видає затравочний піксел
Pop - процедура, що витягає піксел зі стека
Push - процедура, що поміщає піксел у стек
Ініціалізуємо стек
Push Запал(х, у)
While (стек не порожній)
Вибираємо піксел зі стека і привласнюємо йому нове значення
Pop Піксел(х, у)
Піксел(х, у)=Нове_значення
Зберігаємо х-координату затравочного піксела
ТимЧас_х=х
Заповнюємо інтервал праворуч від запалу
х=х+1
while Піксел(х, у)<>Гран_значення
Піксел(х, у)=Нове_значення
х=х+1
end while
зберігаємо крайній праворуч піксел
Хправ=х-1
Відновлюємо х-координату запалу
х=ТимЧас_х
заповнюємо інтервал ліворуч від запалу
х=х-1
While Піксел(х, у)<>Гран_значення
Піксел(х, у)=Нове_значення
х=х-1
end while
зберігаємо крайній ліворуч піксел
Хлів=х+1
Відновлюємо х-координату запалу
х=ТимЧас_х
перевіримо, що рядок вище не є ні границею багатокутника, ні вже цілком заповнений; якщо це не так, то знайти запал, починаючи з лівого краю підінтервала скануючого рядка.
х=Хлів
у=у+1
while х ? Хправ
шукаємо запал на рядку вище
Прапор=0
While (Піксел(х, у)<>Гран_значення and
Піксел(х, у)<>Нове_значення and х<Хправ
If Прапор=0 then Прапор=1
х=х+1
end while
поміщаємо в стек крайній правий піксел
if Прапор=1 then
if (х=Хправ and Піксел(х, у)<>Гран_значення
and Піксел(х, у)<>Нове_значення) then
Push Піксел(х, у)
Else
Push Піксел(х-1, у)
End if
Прапор=0
End if
Продовжимо перевірку, якщо інтервал був перерваний
Хвход=х
While ((Піксел(х, у)=Гран_значення or Піксел(х, у)=Нове_значення)
and х<Хправ)
х=х+1
end while
упевнимося, что координата піксела збільшена
if х=Хвход then х=х+1
end while
перевіримо, що рядок нижче не є ні границею багатокутника, ні вже цілком заповнений
ця частина алгоритму зовсім аналогічна перевірці для рядка вище, за винятком того, що замість у=у+1 треба поставити у =у-1
end while
finish
Тут функція Pop вибирає координати х, у піксела із стека, а функція Push поміщає їх у стек.
Текст програми:
//---------------------------------------------------------------------------
#include <vcl.h>
#include <mmsystem.h>
#pragma hdrstop
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
TColor newcol,oldcol;
int x,y;
int ig, ix[350][10], c;
//-----------------------------------------------------...
